#define _CRT_SECURE_NO_WARNINGS   1

//struct ListNode* insertionSortList(struct ListNode* head) {
//    struct ListNode* cur = head->next;
//    while (cur)
//    {
//        if (head->val > cur->val)
//        {
//            struct ListNode* tmp = cur;
//            cur = cur->next;
//            tmp->next = head;
//            head = cur;
//            break;
//
//        }
//        struct ListNode* cpre = head;
//        struct  ListNode* cmp = head->next;
//
//        while (cmp != cur)
//        {
//            cpre = head;
//            cmp = head->next;
//
//            if (cmp->val > cur->val)
//            {
//                struct ListNode* tmp = cur;
//                cmp->next = cur->next;
//                tmp->next = cmp;
//                
//                cpre->next = cmp;
//                break;
//            }
//            cpre = cpre->next;
//            cmp = cmp->next;
//            
//        }
//        cur = cur->next;
//      
//
//    }
//
//    return head;
//

//
//struct ListNode* insertionSortList(struct ListNode* head) {
//    if (!head) return NULL;
//    struct ListNode* dummy = (struct ListNode*)malloc(sizeof(struct ListNode));
//    dummy->next = head;/*  */
//    dummy->val = -1;
//    struct ListNode* cur = head->next;
//    struct ListNode* cpre = dummy;
//    struct ListNode* cmp = dummy->next;
//    while (head)
//    {
//        cur = head->next;
//        cpre = dummy;
//        cmp = dummy->next;
//        while (cmp != cur)
//        {
//            if (cur->val < cmp->val)
//            {
//                head->next = cur->next;
//                cur->next = cmp;
//                cpre->next = cur;
//                break;
//            }
//            cpre = cpre->next;/*  */
//            cmp = cmp->next;
//
//        }
//        head = head->next;
//    }
//
//    struct ListNode* sorted_head = dummy->next;
//    free(dummy);
//    return sorted_head;
//
//
//
//}